#include <iostream>
#include <ctime>
#include <cassert>
#include <algorithm>
#include <typeinfo>
#include <cmath>
#include "Heap.h"
#include "InsertSort.h"
#include "MergeSort.h"
#include "QuickSort.h"
#include "TestSortHelper.h"

using namespace std;

template <typename T>
void heapSort1(T arr[], int n) {
    MaxHeap<int> heap = MaxHeap<int>(n);
    for(int i = 0;i<n;i++){
        heap.insert(arr[i]);
    }
    for(int i = n-1;i>=0;i--){
        arr[i]=heap.pop();
    }
}

template <typename T>
void heapSort2(T arr[], int n) {
    MaxHeap<int> heap = MaxHeap<int>(arr,n);
    for(int i = n-1;i>=0;i--){
        arr[i]=heap.pop();
    }
}

int main(){

    int n = 1000000;
    cout << "Test for Random Array, size = " << n << ", randome range [0, " << n << "]" << endl;
    int *arr1 = TestSortHelper::generateRandomArray(n, 0, n);
    int *arr2 = TestSortHelper::copyIntArray(arr1, n);
    int *arr3 = TestSortHelper::copyIntArray(arr1, n);
    int *arr4 = TestSortHelper::copyIntArray(arr1, n);
    int *arr5 = TestSortHelper::copyIntArray(arr1, n);


    TestSortHelper::testSort("merge up-bottom Sort Sort", mergeSortUB, arr1, n);
    TestSortHelper::testSort("quick Sort 2 double sort", quickSort2, arr2, n);
    TestSortHelper::testSort("quick Sort 3 ways sort", quickSort3, arr3, n);
    TestSortHelper::testSort("heap Sort 1 ", heapSort1, arr4, n);
    TestSortHelper::testSort("heap Sort 2 ", heapSort2, arr5, n);

    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;
    delete[] arr5;


    int swaptimes = 10;
    cout << "Test for Nearly Ordered Array, size = " << n << ", randome range [0, " << n << "]" << endl;
    arr1 = TestSortHelper::generateNearlyOrderedArray(n, swaptimes);
    arr2 = TestSortHelper::copyIntArray(arr1, n);
    arr3 = TestSortHelper::copyIntArray(arr1, n);
    arr4 = TestSortHelper::copyIntArray(arr1, n);
    arr5 = TestSortHelper::copyIntArray(arr1, n);


    TestSortHelper::testSort("merge up-bottom Sort Sort", mergeSortUB, arr1, n);
    TestSortHelper::testSort("quick Sort 2 double sort", quickSort2, arr2, n);
    TestSortHelper::testSort("quick Sort 3 ways sort", quickSort3, arr3, n);
    TestSortHelper::testSort("heap Sort 1", heapSort1, arr4, n);
    TestSortHelper::testSort("heap Sort 2 ", heapSort2, arr5, n);

    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;
    delete[] arr5;

    int range = 10;
    cout << "Test for Nearly Ordered Array, size = " << n << ", randome range [0, " << range << "]" << endl;
    arr1 = TestSortHelper::generateNearlyOrderedArray(n, swaptimes);
    arr2 = TestSortHelper::copyIntArray(arr1, n);
    arr3 = TestSortHelper::copyIntArray(arr1, n);
    arr4 = TestSortHelper::copyIntArray(arr1, n);
    arr5 = TestSortHelper::copyIntArray(arr1, n);


    TestSortHelper::testSort("merge up-bottom Sort Sort", mergeSortUB, arr1, n);
    TestSortHelper::testSort("quick Sort 2 double sort", quickSort2, arr2, n);
    TestSortHelper::testSort("quick Sort 3 ways sort", quickSort3, arr3, n);
    TestSortHelper::testSort("heap Sort 1", heapSort1, arr4, n);
    TestSortHelper::testSort("heap Sort 2 ", heapSort2, arr5, n);

    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;
    delete[] arr5;

    return 0;
}

